Mechagodzilla

Limit pamięci: 128 MB

Przedwczoraj sam byłeś świadkiem, jak Godzilla zjadała kable z Modą na sukces. Władze Bajtołów Dolnych postanowiły powiedzieć Godzilli stanowcze nie. Do walki z Godzillą zaprzęgli Mechagodzillę, która w odróżnieniu od tej pierwszej jest robotem, którym mogą sterować. Mechagodzilla ma stanów, w których może się znajdować, w tym jeden stan początkowy i pewien podzbiór stanów bojowych. W każdym stanie Mechagodzilla może wykonać jedną z instrukcji (instrukcje są oznaczone wielkimi literami od A do Z), które powodują zmianę stanu na inny. Jeśli Mechagodzilla jest w stanie i otrzyma instrukcję , to przechodzi do stanu .

Grupa informatłuków pisze program dla Mechagodzilli. Jest to ciąg instrukcji, które Mechagodzilla wykonuje kolejno, zaczynając od stanu początkowego. Powiemy, że program jest dobry, jeśli Mechagodzilla po jego zakończeniu znajdzie się w stanie bojowym. Informatłucy mają to do siebie, że co chwilę robią w programie jakieś poprawki, polegające na zamianie miejscami pewnych dwóch instrukcji. Twoim zadaniem jest odpowiadać na pytania, czy po danej zamianie program jest dobry czy nie.

Wejście

Pierwszy wiersz wejścia zawiera cztery liczby naturalne (, , , ), oznaczające odpowiednio liczbę stanów, liczbę stanów bojowych, długość programu i liczbę poprawek dokonanych przez informatłuków.

Następny wiersz zawiera liczb naturalnych (), które oznaczają numery stanów bojowych. Stan o numerze to stan początkowy.

Następne wierszy zawiera po liczb naturalnych (), oznaczających, że jeśli Mechagodzilla będzie w stanie i dostanie instrukcję , to przejdzie do stanu .

Następny wiersz zawiera napis złożony z wielkich liter alfabetu angielskiego, oznaczających program dla Mechagodzilli.

Następne wierszy zawiera po dwie liczby naturalne (), oznaczające kolejne poprawki informatłuków. Każda taka poprawka oznacza, że instrukcje na pozycjach i zamieniają się miejscami.

Wyjście

Na wyjściu należy wypisać wierszy. Są to odpowiedzi na pytania, czy po kolejnych poprawkach program jest dobry (TAK jeśli tak, NIE w przeciwnym wypadku).

Przykład

Dla danych wejściowych:

3 1 5 2
3
1 1 1 1 1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1
TKOAN
1 3
2 5

poprawną odpowiedzią jest:

NIE
TAK

Autor zadania: Dariusz Leniowski.